#lang racket

(require "rename-mutable-pair-ops.rkt")

(provide make-table insert! lookup print-table)

;RECORD OPERATIONS-------------------------------------------------------------------------------

(define (make-record key data)
  (cons key data))

(define (key record)
  (car record))

(define (data record)
  (cdr record))

(define (set-key! key record)
  (set-car! record key))

(define (set-data! data record)
  (set-cdr! record data))

;TREE SELECTORS AND CONSTRUCTORS-----------------------------------------------------------------

(define (entry tree) (car (cdr tree)))

(define (left-branch tree) (car (cdr (cdr tree))))

(define (right-branch tree) (car (cdr (cdr (cdr tree)))))

(define (set-entry! entry tree)
  (set-car! (cdr tree) entry))

(define (set-left-branch! tree left-branch)
  (set-car! (cdr (cdr tree)) left-branch))

(define (set-right-branch! tree right-branch)
  (set-car! (cdr (cdr (cdr tree))) right-branch))

(define (make-tree entry left right)
  (list '*tree* entry left right))

(define (make-empty-tree) (list '*tree* '() '() '()))

;INTERFACE PROCEDURES----------------------------------------------------------------------------

(define make-table make-empty-tree)

(define print-table print-list)

(define (lookup given-key tree)
  (cond ((null? tree) false)
        ((= given-key (key (entry tree))) (data (entry tree)))
        ((< given-key (key (entry tree)))
         (lookup given-key (left-branch tree)))
        ((> given-key (key (entry tree)))
         (lookup given-key (right-branch tree)))))

(define (insert! given-key value tree)
  (cond ((null? (entry tree))
         (set-entry! (make-record given-key value) tree))
        ((= given-key (key (entry tree)))
         (set-data! value (entry tree)))
        ((< given-key (key (entry tree)))
         (if (null? (left-branch tree))
             (set-left-branch! tree (make-tree (make-record given-key value) '() '()))
             (insert! given-key value (left-branch tree))))
        ((> given-key (key (entry tree)))
         (if (null? (right-branch tree))
             (set-right-branch! tree (make-tree (make-record given-key value) '() '()))
             (insert! given-key value (right-branch tree))))))
